#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: set_count.py 
@version:
@time: 2024/01/17 

将由m个元素组成的集合拆分成m个非空子集，假设函数名为f。
若想将n个元素分成m组，就需要考虑第n个元素需要放在什么位置，剩余元素需要被放在多少个分组中。

第n个元素有两种选择：
一是将第n个元素单独成一组，则剩余n-1个元素应当被分在m-1个组中，执行递归调用f(n-1,m-1)；

二是将第n个元素放到m个已经分好的组中的一组里，在m个组中选择一个组有m中选择方式，
则剩余n-1个元素应当被分在m组中，执行递归调用mf(n-1,m)，

两种分组方式累加即为将n个元素分为m组的总集合数。

因此，递归关系式如下:

    f(n,m)=mf(n-1, m)+f(n-1,m-1)

递归终止条件为当元素总数与分组数相等时，只有一种分组方式；或者当分组数m为1时，也只有一种分组方式。
"""


def set_count(n, m):
    if m == 1 or n == m:
        return 1
    else:
        return set_count(n - 1, m - 1) + set_count(n - 1, m) * m


print(set_count(5, 2))
